1. Field of the Invention
The invention relates to a data filtering scheme with multiple filters.
2. Description of the Related Technology
In a cable television system, a cable headend often sends a large amount of network traffic to a set top box (STB). The set top box needs to examine each data packet and find the data patterns matching the data packet for further processing. Different data patterns are provided by the headend with multiple filters, and these patterns can be changed or adjusted by the headend. This makes it difficult to apply existing data filtering algorithms which use fixed data pattern for filtering, such as the data filtering algorithms used in IP packet filtering or IP firewall protection.
Filters in a cable STB exist in the form of a (n×m) matrix, where n and m is the number of rows and columns, respectively. Let fij represents a filter located in i-th row and j-th column in the matrix. All the conditions of each filter in the i-th row (i.e. fi0, fi1, . . . fim) must be satisfied when evaluating the filters in the row. In other words, the evaluation of filters in the row uses AND operator. However, OR operator is used for the evaluation of filters in j-th columns (i.e. f0j, fij, . . . , fmj)). Traditional data filtering is done “sequentially”, that is, full filtering starts with at the 0-th row (i.e. f00, f01, . . . , f0m). If 0-th row is not satisfied, then it moves on to the next row until one finds the correct set of filters in a specific row. Typically, a packet is sequentially compared to each filter until a match, or dropped after comparing to the last filter.
The data filtering requires a large amount of processing time and resources. Given that the traditional data filtering scheme is computationally complex, it is desirable to find an improved scheme with reduced computational complexity.